#二分kmeans算法
#先对初始的数据分为两类，记录SSE
import numpy
from matplotlib import pyplot
data=numpy.loadtxt('./testSet.txt')
def kmeans(data):
    length=len(data)
    index=numpy.random.permutation(length)[0:2]
    print(index)
    #随机选出2个中心点
    old_centre_point=data[index]
    new_centre_point=old_centre_point.copy()
    first=True
    print(old_centre_point)
    while numpy.any(old_centre_point!=new_centre_point) or first==True:#当前后两次的中心点相同时停止循环,全为False时候才返回False
        old_centre_point = new_centre_point.copy()#记录上一次的值
        distance_class=numpy.empty((2,length))
        for j in range(2):
            for i in range(length):
                distance_class[j,i]=numpy.sqrt(numpy.sum((data[i]-old_centre_point[j])**2))
        class_index=numpy.argmin(distance_class,axis=0)
        dic_class={}
        for i in  range(2):
            dic_class[i]=data[class_index==i]
        #下面重新计算中心点
        for i in range(2):
            new_centre_point[i]=numpy.sum(dic_class[i],axis=0)/len(dic_class[i])
        #必须记录前后中心点的记录
        print(old_centre_point)
        first=False
    distance=numpy.empty(2)
    for i ,j in dic_class.items():
        distance[i]=numpy.sum((j-old_centre_point[i])**2)
    return distance,[dic_class[0],dic_class[1]]
def kmeanspp(data):
    length = len(data)
    # 先随机选出一个中心点
    index = numpy.random.randint(length, size=1)
    # 再用kmeans++算法选出其他三个点
    while len(index) < 4:
        centre_point = data[index]
        shape = centre_point.shape
        distance2 = numpy.empty((shape[0], length))
        p = numpy.empty(length)
        for j in range(shape[0]):
            for i in range(length):
                distance2[j, i] = numpy.sum((data[i] - centre_point[j]) ** 2)
        distance = numpy.min(distance2, axis=0)
        sum = numpy.sum(distance)
        for i in range(length):
            p[i] = distance[i] / sum
        cump = numpy.cumsum(p)
        a = numpy.random.rand(1)
        if a[0] <= cump[0]:
            index = numpy.append(index, numpy.array([0]), axis=0)
        else:
            index = numpy.append(index, numpy.array([len(cump[cump < a])]), axis=0)
    old_centre_point = data[index]
    new_centre_point = old_centre_point.copy()
    first = True
    print(old_centre_point)
    # 选出初始中心点后，再进行迭代
    while numpy.any(old_centre_point != new_centre_point) or first == True:  # 当前后两次的中心点相同时停止循环,全为False时候才返回False
        old_centre_point = new_centre_point.copy()  # 记录上一次的值
        distance_class = numpy.empty((4, length))
        for j in range(4):
            for i in range(length):
                distance_class[j, i] = numpy.sqrt(numpy.sum((data[i] - old_centre_point[j]) ** 2))
        class_index = numpy.argmin(distance_class, axis=0)
        dic_class = {}
        for i in range(4):
            dic_class[i] = data[class_index == i]
        # 下面重新计算中心点
        for i in range(4):
            new_centre_point[i] = numpy.sum(dic_class[i], axis=0) / len(dic_class[i])
        # 必须记录前后中心点的记录
        print(new_centre_point)
        first = False
    # 收敛速度得到提升
    return distance, [dic_class[0], dic_class[1]]
#利用kmeans算法的bikmeans,先将其分为两类
distance0,cl0=kmeans(data)
while len(cl0)<4:
    clli=[]
    sseli=[]
    distanceli=[]
    for i in range(len(cl0)):
        distance,cl=kmeans(cl0[i])
        clli.append(cl)
        sseli.append(distance0[i]-numpy.sum(distance))
        distanceli.append(distance)
    index=numpy.argmax(sseli)
    cl0=cl0[:index]+cl0[index+1:]
    cl0.extend(clli[index])
    distance0=numpy.r_[distance0[:index],distance0[index+1:]]
    distance0=numpy.r_[distance0,distanceli[index]]
for i in range(len(cl0)):
    pyplot.scatter(cl0[i][:,0],cl0[i][:,1])
pyplot.savefig('./my_bikmeans.jpg')
pyplot.show()
#利用kmeans++算法的bikmeans
distance0,cl0=kmeanspp(data)
while len(cl0)<4:
    clli=[]
    sseli=[]
    distanceli=[]
    for i in range(len(cl0)):
        distance,cl=kmeanspp(cl0[i])
        clli.append(cl)
        sseli.append(distance0[i]-numpy.sum(distance))
        distanceli.append(distance)
    index=numpy.argmax(sseli)
    cl0=cl0[:index]+cl0[index+1:]
    cl0.extend(clli[index])
    distance0=numpy.r_[distance0[:index],distance0[index+1:]]
    distance0=numpy.r_[distance0,distanceli[index]]
